package com.leetcode.algorithm.y22.m06;

/**
 * 74. 搜索二维矩阵
 * 
 * https://leetcode.cn/problems/search-a-2d-matrix/
 * 
 * @author jie.deng
 *
 */
class Question0074Solution01 {

	public boolean searchMatrix(int[][] matrix, int target) {
		int m = matrix.length;
		int n = matrix[0].length;
		int left = 0;
		int right = m * n - 1;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			int r = mid / n;
			int c = mid % n;
			if (matrix[r][c] == target) {
				return true;
			} else if (matrix[r][c] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return false;
	}

}